package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/7-08-07-18:24
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen  KMP算法
 */
/*
KMP算法
    用于文本匹配的算法，属于模式搜索问题的一种算法，
    通过省略主串（待匹配的杂乱字符串）索引的回溯，尽可能减少反复次数，使字符串匹配效率有了莫种程度的提升
 */
public class KMP {
    public static void main(String[] args) {
        String str1 = "ABABABABCABAAB";
//        String str1 = "auissuie Hello worll? hello worrowhhhello worldss ";
        String str2 = "ABABCABAA";
//        String str2 = "hello world";
        int start = kmp(str1,str2);
        System.out.println(start);
        if(start == -1){
            System.out.println("匹配失败！");
        }else{
            System.out.println(start + "~" + (start+str2.length()) + "匹配成功");
        }
    }

    public static int kmp(String str1, String str2) {
        int[] next = getNext(str2);      //获取next数组
        int start = -1;       //记录开始匹配的位置
        int j = 0,k = 0;
       for(int i = 0;i <= str1.length() - str2.length();i++){        //开始匹配
            start = i;
            k = i;             //要匹配的位置的下标
            for (j = 0; j < str2.length(); j++) {
                if(str1.charAt(k) != str2.charAt(j)){
                    i = next[j] + i;        //按照next【j】移动str1的下标i
                    break;
                }
                k++;
            }
            if(j >= str2.length()){     //匹配成功
                return start;
            }
        }
        return -1;
    }

    /**
     * 提取模式串对应的next数组
     * @param str2   模式字符串
     * @return     next数组
     */
    public static int[] getNext(String str2) {
        int[] next = new int[str2.length()];
        int len;

        for (int i = 1; i < str2.length(); i++) {
            len = next[i-1];
            while(len >= 0){
                if(str2.charAt(i) == str2.charAt(len)){
                    next[i] = len+1;
                    break;
                }
                if(len == 0){
                    break;
                }
                len = next[len-1];
            }
        }
        System.out.println(Arrays.toString(next));
        return next;
    }
}
